/*
给你一个数组A[1..n]，
请你在O(n)的时间里构造一个新的数组B[1..n]，
使得
     B[i]=A[1]*A[2]*…*A[n]/A[i] 
你不能使用除法运算。 
*/

#include "junix.h"
using namespace std;

int f(int a, int b) {
	if (a==b) return 1;
	return a;
}

int g(int v[], int size, int b) {
	int result = 1;
	for (int i=0;i<size;i++) 
		result *= f(v[i],b);

	return result;
}

void cal(int s[], int d[], int size) {
	int factor[size], reverse_factor[size];
	factor[0]=s[0];
	reverse_factor[size-1] = s[size-1];

	for (int i=1;i<size;i++) {
		factor[i]=factor[i-1]*s[i];
		reverse_factor[size-i-1] = reverse_factor[size-i]*s[size-i-1];
	}

	d[0]=reverse_factor[1];
	d[size-1]=factor[size-2];
	for (int i=1;i<size-1;i++) 
		d[i] = factor[i-1]*reverse_factor[i+1];
}

int main(int argc, char **argv)
{
	int v[]={1,2,3,4,5,6,7,8,9};
	int d[9];
	const int sz=sizeof(v)/sizeof(v[0]);
	cal(v,d,sz);
	copy(d,d+sz,std::ostream_iterator<int>(std::cout," "));
	std::cout<<std::endl;

	for (int i=0;i<sz;i++)
		assert(d[i]==g(v,sz,v[i]));
}
